การเพิ่มประสิทธิภาพคือ กระบวนการทางคณิตศาสตร์ในการหาคำตอบที่ดีที่สุด—ทั้งในแง่ของการลดหรือเพิ่มฟังก์ชันวัตถุประสงค์—ภายในพื้นที่ที่เป็นไปได้ที่กำหนดไว้ ภายใต้ข้อจำกัดเฉพาะบางประการ
วิธีการคลาสสิกเทียบกับวิธีการอัจฉริยะ
- วิธีนิวตัน-ราฟสัน:แนวทางการหาค่ารากแบบวนซ้ำ โดยใช้อนุพันธ์อันดับสอง (เมทริกซ์เฮสเซียน)
- การลดความชัน:วิธีอันดับแรกที่เคลื่อนที่ไปยังจุดต่ำสุดท้องถิ่นโดยตามแนวลบของอนุพันธ์
- อัลกอริธึมเชิงวิวัฒนาการ (เอเอส):วิธีการค้นหาแบบสุ่มที่อิงจากประชากร และได้แรงบันดาลใจจากธรรมชาติการเลือกสรรทางชีวภาพ
แนวคิดสำคัญ
สิ่งสำคัญคือ การแยกแยะระหว่างเวกเตอร์การตัดสินใจ (ตัวแปรที่เราเปลี่ยนแปลง) กับฟังก์ชันวัตถุประสงค์ (ตัวชี้วัดความสำเร็จ)
ข้อผิดพลาดในการเข้ารหัส
ระวังเรื่องความชันหายไป ในวิธีที่อาศัยแคลคูลัส และโคลนแฮมมิง ในอัลกอริธึมเชิงวิวัฒนาการที่เข้ารหัสเป็นเลขฐานสอง ซึ่งการเพิ่มทีละหน่วย (เช่น จาก 7 เป็น 8) อาจต้องสลับบิตทุกตัว (0111 → 1000) ทำให้เกิด "หุบเขา" ที่ขัดขวางประสิทธิภาพในการค้นหา ควรใช้การเข้ารหัสเกรย์ เพื่อลดปัญหานี้
การใช้งานภาษาไพธอน: การลดความชัน
คำถามข้อที่ 1
ทำไมปัญหาการเพิ่มประสิทธิภาพแบบโค้งเว้าถึงถือว่า "ง่ายกว่า" ปัญหาแบบไม่โค้งเว้า?
คำถามข้อที่ 2
ในบริบทของอัลกอริธึมเชิงวิวัฒนาการ "เฟโนไทป์" หมายถึงอะไร?
กรณีศึกษา: การเพิ่มพื้นที่สามเหลี่ยมให้สูงสุด
อ่านสถานการณ์ด้านล่าง และตอบคำถามเกี่ยวกับการจัดรูปแบบ
พิจารณาปัญหาการหาพื้นที่สามเหลี่ยมมุมฉากที่ใหญ่ที่สุด โดยที่ความยาวด้านตรงข้ามมุมฉาก $c$ ถูกกำหนดคงที่ไว้
คำถาม
1. ระบุตัวแปรการตัดสินใจ และฟังก์ชันวัตถุประสงค์
คำตอบ:
ตัวแปร: ความยาวของด้านประกอบมุมฉากสองด้าน คือ $a$ และ $b$
ฟังก์ชันวัตถุประสงค์: หาค่าที่มากที่สุดของ $Area = \frac{1}{2} \cdot a \cdot b$.
ตัวแปร: ความยาวของด้านประกอบมุมฉากสองด้าน คือ $a$ และ $b$
ฟังก์ชันวัตถุประสงค์: หาค่าที่มากที่สุดของ $Area = \frac{1}{2} \cdot a \cdot b$.
คำถาม
2. ระบุเงื่อนไขตามคุณสมบัติทางเรขาคณิต
คำตอบ:
อ้างอิงจากกฎพีทาโกรัส เงื่อนไขคือ: $a^2 + b^2 = c^2$.
อ้างอิงจากกฎพีทาโกรัส เงื่อนไขคือ: $a^2 + b^2 = c^2$.
คำถาม
3. หากใช้วิธีนิวตัน-ราฟสัน ต้องคำนวณเมทริกซ์ใดเพื่อสะท้อนอนุพันธ์อันดับสองบางส่วน?
คำตอบ:
เมทริกซ์เฮสเซียน ($H$) ซึ่งประกอบด้วยอนุพันธ์อันดับสองทั้งหมดของฟังก์ชันวัตถุประสงค์
เมทริกซ์เฮสเซียน ($H$) ซึ่งประกอบด้วยอนุพันธ์อันดับสองทั้งหมดของฟังก์ชันวัตถุประสงค์